package dp;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class ContiguousArray525 {
    @Test
    public void test() {
        findMaxLength(new int[]{0, 1});
        findMaxLength(new int[]{0, 1, 0});
        findMaxLength(new int[]{0, 1, 1, 0});
        findMaxLength(new int[]{0, 1, 0, 1});
        findMaxLength(new int[]{0,0,1,0,0,0,1,1});
    }

    public int findMaxLength(int[] n) {
        // diff[i+1] = count of 1 minus count of 0 till index i (inclusive).
        int[] diff = new int[n.length+1];
        diff[0] = 0;
        // i-1 -> i
        int maxLen = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(diff[0], 0);
        for (int i = 1; i <= n.length; i++) {
            diff[i] = diff[i-1] + (n[i-1] == 1 ? 1 : -1);
            if (map.containsKey(diff[i])) {
                // 注意, 这里不需要替换, 要让map中的value(index)尽量小
                int prevIndex = map.get(diff[i]);
                maxLen = Math.max(maxLen, i - prevIndex);
            } else {
                map.put(diff[i], i);
            }
        }
        System.out.format("n: %s, maxLen: %d\n", Arrays.toString(n), maxLen);
        return maxLen;
    }

    // 方法没问题, 超时了, 要用HashMap保存前缀和
    public int findMaxLength1(int[] n) {
        // diff[i+1] = count of 1 minus count of 0 till index i (inclusive).
        int[] diff = new int[n.length+1];
        diff[0] = 0;
        // i-1 -> i
        for (int i = 1; i <= n.length; i++) {
            diff[i] = diff[i-1] + (n[i-1] == 1 ? 1 : -1);
        }

        int maxLen = 0;
        // 注意边界,j可以为0
        for (int i = 1; i <= n.length; i++) {
            for (int j = i-1; j >= 0; j--) {
                // 注意这里是减号,不是加号
                if (diff[i] - diff[j] == 0) {
                    maxLen = Math.max(maxLen, i-j);
                }
            }
        }
        System.out.format("n: %s, maxLen: %d\n", Arrays.toString(n), maxLen);
        return maxLen;
    }
}
